UVa/11336 - DRM/drm.cpp

   1 #include <iostream>
   2 #include <map>
   3 #include <vector>
   4 #include <string>
   5 #include <sstream>
   6 #include <set>
   7
   8 using namespace std;
   9
  10 typedef string node;
  11 typedef pair<node, node> edge;
  12 typedef map<node, vector<node> > graph;
  13
  14 bool dfs(node v, node destiny, set<node> visited, const graph &g, const set<node> &forbidden){
  15   vector<node> neighbors = (*(g.find(v))).second;
  16   for (int i=0; i<neighbors.size(); ++i){
  17     if (neighbors[i] == destiny) return true;
  18     if (!(visited.count(neighbors[i])) && !(forbidden.count(neighbors[i]))){
  19       set<node> temp = visited;
  20       temp.insert(v);
  21       if (dfs(neighbors[i], destiny, temp, g, forbidden)){
  22         return true;
  23       }
  24     }
  25   }
  26   return false;
  27 }
  28
  29 bool validate(edge e, const graph &g, const set<node> &forbidden){
  30   set<node> visited;
  31   return (dfs(e.first, e.second, visited, g, forbidden));
  32 }
  33
  34 int main(){
  35   string name1, name2;
  36   while (getline(cin, name1) && name1 != "END"){
  37     graph g;
  38     set<node> forbidden;
  39     string line;
  40     vector<edge> streets;
  41     while (getline(cin, line) && line != "* * *"){
  42       stringstream sin;
  43       sin << line;
  44       edge e;
  45       sin >> e.first >> e.second;
  46       streets.push_back(e);
  47       forbidden.insert(e.first);
  48       forbidden.insert(e.second);
  49     }
  50
  51     getline(cin, name2);
  52     while (getline(cin, line) && line != "* * *"){
  53       stringstream sin;
  54       sin << line;
  55       edge e;
  56       sin >> e.first >> e.second;
  57       vector<node> v;
  58       if (g.count(e.first) == 0){
  59         g[e.first] = v;
  60       }
  61       if (g.count(e.second) == 0){
  62         g[e.second] = v;
  63       }
  64       g[e.first].push_back(e.second);
  65       g[e.second].push_back(e.first);
  66     }
  67
  68     //Terminé la lectura
  69     for (set<node>::iterator it = forbidden.begin(); it != forbidden.end(); ++it){
  70       if (g.count((*it)) == 0){
  71         cout << "NO: " << name2 <<" is not a more detailed version of " << name1 << endl;
  72         continue;
  73       }
  74     }
  75     bool impossible = false;
  76     for (int i=0; i<streets.size(); ++i){
  77       if (!validate(streets[i], g, forbidden)){
  78         impossible = true;
  79         break;
  80       }
  81     }
  82     if (impossible){
  83       cout << "NO: " << name2 <<" is not a more detailed version of " << name1 << endl;
  84     }else{
  85       cout << "YES: " << name2 <<" is a more detailed version of " << name1 << endl;
  86     }
  87   }
  88   return 0;
  89 }